

#include "stdafx.h"

#include "Utils.h"


#define M 5

int aMap[M][M] = { {7,0,0,0,0},
				   {3,8,0,0,0},
				   {8,1,0,0,0},
				   {2,7,4,4,0},
				   {4,5,2,6,5} };
int aMaxSum[M][M] = { 0 };
int aMen[M][M];

#ifdef TEST_BED
int main()
#else
int main_()
#endif
{
	//Step0. Init aMen[M][M]
	for (int i = 0; i < M; i++)
		for (int j = 0; j < M; j++)
			aMen[i][j] = -1;

	//Step1. Init aMaxSum[M][M]
	for (int i = 0; i < M; i++)
		aMaxSum[M - 1][i] = aMap[M - 1][i];


	//Step2. Backstepping up
	//Recursion Formula is aMaxSum[i][j] = MAX(aMaxSum[i+1][j], aMaxSum[i+1][j+1]) + aMap[i][j];
	int maxVal;
	for (int i = M - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (aMaxSum[i][j] > aMaxSum[i][j + 1]) {
				aMen[i - 1][j] = 0;
				maxVal = aMaxSum[i][j];
			}
			else {
				aMen[i - 1][j] = 1;
				maxVal = aMaxSum[i][j+1];
			}
			aMaxSum[i - 1][j] = maxVal + aMap[i - 1][j];
		}
	}


	int ds = 0;
	for (int i = 0; i < M; i++) {	
		printf("line %d: value = %d\n", i+1, aMap[i][ds]);
		ds += aMen[i][ds];
	}

    return 0;
}


#if 0

#endif

#if 0
//Step1. Init aMaxSum[M]
int sum = 0;
for (int i = 0; i < M; i++) {
	sum += aMap[i][0];
	aMaxSum[i][0] = sum;
}

//Step2. Backstepping down
//Recursion Formula is aMaxSum[i][j] = MAX(aMaxSum[i-1][j-1], aMaxSum[i-1][j]) + aMap[i][j];
for (int i = 1; i < M; i++) {
	for (int j = 1; j <= i; j++) {
		aMaxSum[i][j] = MAX(aMaxSum[i - 1][j - 1], aMaxSum[i - 1][j]) + aMap[i][j];
	}
}

for (int i = 0; i < M; i++)
	printf("maxSum = %d\n", aMaxSum[M - 1][i]);
#endif
